<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xml:lang="en" lang="en">
<!-- Created by GNU Texinfo 5.1, http://www.gnu.org/software/texinfo/ -->
<head>
<title>Structure and Interpretation of Computer Programs, 2e: 5.3</title>

<meta name="description" content="Structure and Interpretation of Computer Programs, 2e: 5.3" />
<meta name="keywords" content="Structure and Interpretation of Computer Programs, 2e: 5.3" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<meta name="Generator" content="texi2any" />
<meta charset="utf-8" />
<link href="index.xhtml#Top" rel="start" title="Top" />
<link href="Term-Index.xhtml#Term-Index" rel="index" title="Term Index" />
<link href="index.xhtml#SEC_Contents" rel="contents" title="Table of Contents" />
<link href="Chapter-5.xhtml#Chapter-5" rel="prev" title="Chapter 5" />
<link href="5_002e4.xhtml#g_t5_002e4" rel="next" title="5.4" />
<link href="5_002e2.xhtml#g_t5_002e2_002e4" rel="prev" title="5.2.4" />

<link href="css/style.css" rel="stylesheet" type="text/css" />
<link href="css/prettify.css" rel="stylesheet" type="text/css" />

<script src="js/jquery.min.js" type="text/javascript"></script>
<script src="js/footnotes.js" type="text/javascript"></script>
<script src="js/browsertest.js" type="text/javascript"></script>
</head>

<body>
<section><span class="top jump" title="Jump to top"><a href="#pagetop" accesskey="t">⇡</a></span><a id="pagetop"></a><a id="g_t5_002e3"></a>
<nav class="header">
<p>
Next: <a href="5_002e4.xhtml#g_t5_002e4" accesskey="n" rel="next">5.4</a>, Prev: <a href="5_002e2.xhtml#g_t5_002e2" accesskey="p" rel="prev">5.2</a>, Up: <a href="Chapter-5.xhtml#Chapter-5" accesskey="u" rel="prev">Chapter 5</a>   [<a href="index.xhtml#SEC_Contents" title="Table of contents" accesskey="c" rel="contents">Contents</a>]</p>
</nav>
<a id="Storage-Allocation-and-Garbage-Collection"></a>
<h3 class="section"><span class="secnum">5.3</span><span class="sectitle">Storage Allocation and Garbage Collection</span></h3>

<p>In section <a href="5_002e4.xhtml#g_t5_002e4">5.4</a>, we will show how to implement a Scheme evaluator as a
register machine.  In order to simplify the discussion, we will assume that our
register machines can be equipped with a <a id="index-list_002dstructured-memory"></a>
<em>list-structured memory</em>, in
which the basic operations for manipulating list-structured data are primitive.
Postulating the existence of such a memory is a useful abstraction when one is
focusing on the mechanisms of control in a Scheme interpreter, but this does
not reflect a realistic view of the actual primitive data operations of
contemporary computers.  To obtain a more complete picture of how a Lisp system
operates, we must investigate how list structure can be represented in a way
that is compatible with conventional computer memories.
</p>
<p>There are two considerations in implementing list structure.  The first is
purely an issue of representation: how to represent the “box-and-pointer”
structure of Lisp pairs, using only the storage and addressing capabilities of
typical computer memories.  The second issue concerns the management of memory
as a computation proceeds.  The operation of a Lisp system depends crucially on
the ability to continually create new data objects.  These include objects that
are explicitly created by the Lisp procedures being interpreted as well as
structures created by the interpreter itself, such as environments and argument
lists.  Although the constant creation of new data objects would pose no
problem on a computer with an infinite amount of rapidly addressable memory,
computer memories are available only in finite sizes (more’s the pity).  Lisp
systems thus provide an <a id="index-automatic-storage-allocation"></a>
<em>automatic storage allocation</em> facility to
support the illusion of an infinite memory.  When a data object is no longer
needed, the memory allocated to it is automatically recycled and used to
construct new data objects.  There are various techniques for providing such
automatic storage allocation.  The method we shall discuss in this section is
called <a id="index-garbage-collection"></a>
<em>garbage collection</em>.
</p>
<a id="g_t5_002e3_002e1"></a>
<a id="Memory-as-Vectors"></a>
<h4 class="subsection"><span class="secnum">5.3.1</span><span class="sectitle">Memory as Vectors</span></h4>

<p>A conventional computer memory can be thought of as an array of cubbyholes,
each of which can contain a piece of information.  Each cubbyhole has a unique
name, called its <a id="index-address"></a>
<em>address</em> or <a id="index-location"></a>
<em>location</em>.  Typical memory
systems provide two primitive operations: one that fetches the data stored in a
specified location and one that assigns new data to a specified location.
Memory addresses can be incremented to support sequential access to some set of
the cubbyholes.  More generally, many important data operations require that
memory addresses be treated as data, which can be stored in memory locations
and manipulated in machine registers.  The representation of list structure is
one application of such <a id="index-address-arithmetic"></a>
<em>address arithmetic</em>.
</p>
<p>To model computer memory, we use a new kind of data structure called a
<a id="index-vector"></a>
<em>vector</em>.  Abstractly, a vector is a compound data object whose
individual elements can be accessed by means of an integer index in an amount
of time that is independent of the index.<a class="footnote_link" id="DOCF290" href="#FOOT290"><sup>290</sup></a> In order to describe memory operations, we use two
primitive Scheme procedures for manipulating vectors:
</p>
<ul>
<li> <code>(vector-ref ⟨<var>vector</var>⟩ ⟨<var>n</var>⟩)</code> returns the <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>n</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mtext>th</mtext>
    </mrow>
  </msup>
</math>
element of the vector.

</li><li> <code>(vector-set! ⟨<var>vector</var>⟩ ⟨<var>n</var>⟩ ⟨<var>value</var>⟩)</code>
sets the <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>n</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mtext>th</mtext>
    </mrow>
  </msup>
</math> element of the vector to the designated value.

</li></ul>

<p>For example, if <code>v</code> is a vector, then <code>(vector-ref v 5)</code> gets the
fifth entry in the vector <code>v</code> and <code>(vector-set! v 5 7)</code> changes the
value of the fifth entry of the vector <code>v</code> to 7.<a class="footnote_link" id="DOCF291" href="#FOOT291"><sup>291</sup></a>  For computer memory, this access can
be implemented through the use of address arithmetic to combine a <a id="index-base-address"></a>
<em>base address</em> 
that specifies the beginning location of a vector in memory with an
<a id="index-index"></a>
<em>index</em> that specifies the offset of a particular element of the
vector.
</p>
<a id="Representing-Lisp-data"></a>
<h5 class="subsubheading">Representing Lisp data</h5>

<p>We can use vectors to implement the basic pair structures required for a
list-structured memory.  Let us imagine that computer memory is divided into
two vectors: <code>the-cars</code> and <code>the-cdrs</code>.  We will represent list
structure as follows: A pointer to a pair is an index into the two vectors.
The <code>car</code> of the pair is the entry in <code>the-cars</code> with the designated
index, and the <code>cdr</code> of the pair is the entry in <code>the-cdrs</code> with the
designated index.  We also need a representation for objects other than pairs
(such as numbers and symbols) and a way to distinguish one kind of data from
another.  There are many methods of accomplishing this, but they all reduce to
using <a id="index-typed-pointers"></a>
<em>typed pointers</em>, that is, to extending the notion of “pointer”
to include information on data type.<a class="footnote_link" id="DOCF292" href="#FOOT292"><sup>292</sup></a> The data type
enables the system to distinguish a pointer to a pair (which consists of the
“pair” data type and an index into the memory vectors) from pointers to other
kinds of data (which consist of some other data type and whatever is being used
to represent data of that type).  Two data objects are considered to be the
same (<code>eq?</code>) if their pointers are identical.<a class="footnote_link" id="DOCF293" href="#FOOT293"><sup>293</sup></a> 
<a href="#Figure-5_002e14">Figure 5.14</a> illustrates the use of this method to
represent the list <code>((1 2) 3 4)</code>, whose box-and-pointer diagram is also
shown.  We use letter prefixes to denote the data-type information.  Thus, a
pointer to the pair with index 5 is denoted <code>p5</code>, the empty list is
denoted by the pointer <code>e0</code>, and a pointer to the number 4 is denoted
<code>n4</code>.  In the box-and-pointer diagram, we have indicated at the lower left
of each pair the vector index that specifies where the <code>car</code> and
<code>cdr</code> of the pair are stored.  The blank locations in <code>the-cars</code> and
<code>the-cdrs</code> may contain parts of other list structures (not of interest
here).
</p>
<figure class="float">
<a id="Figure-5_002e14"></a>
<object style="width: 53.44ex; height: 41.96ex;" data="fig/chap5/Fig5.14b.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 5.14:</strong> Box-and-pointer and memory-vector representations of the list <code>((1 2) 3 4)</code>.</p>
</figcaption>
</figure>

<p>A pointer to a number, such as <code>n4</code>, might consist of a type indicating
numeric data together with the actual representation of the number
4.<a class="footnote_link" id="DOCF294" href="#FOOT294"><sup>294</sup></a>  To deal with numbers that are too large to be represented in the
fixed amount of space allocated for a single pointer, we could use a distinct
<a id="index-bignum"></a>
<em>bignum</em> data type, for which the pointer designates a list in which
the parts of the number are stored.<a class="footnote_link" id="DOCF295" href="#FOOT295"><sup>295</sup></a>
</p>
<p>A symbol might be represented as a typed pointer that designates a sequence of
the characters that form the symbol’s printed representation.  This sequence is
constructed by the Lisp reader when the character string is initially
encountered in input.  Since we want two instances of a symbol to be recognized
as the “same” symbol by <code>eq?</code> and we want <code>eq?</code> to be a simple test
for equality of pointers, we must ensure that if the reader sees the same
character string twice, it will use the same pointer (to the same sequence of
characters) to represent both occurrences.  To accomplish this, the reader
maintains a table, traditionally called the <a id="index-obarray"></a>
<em>obarray</em>, of all the
symbols it has ever encountered.  When the reader encounters a character string
and is about to construct a symbol, it checks the obarray to see if it has ever
before seen the same character string.  If it has not, it uses the characters
to construct a new symbol (a typed pointer to a new character sequence) and
enters this pointer in the obarray.  If the reader has seen the string before,
it returns the symbol pointer stored in the obarray.  This process of replacing
character strings by unique pointers is called <a id="index-interning"></a>
<em>interning</em> symbols.
</p>
<a id="Implementing-the-primitive-list-operations"></a>
<h5 class="subsubheading">Implementing the primitive list operations</h5>

<p>Given the above representation scheme, we can replace each “primitive” list
operation of a register machine with one or more primitive vector operations.
We will use two registers, <code>the-cars</code> and <code>the-cdrs</code>, to identify the
memory vectors, and will assume that <code>vector-ref</code> and <code>vector-set!</code>
are available as primitive operations.  We also assume that numeric operations
on pointers (such as incrementing a pointer, using a pair pointer to index a
vector, or adding two numbers) use only the index portion of the typed pointer.
</p>
<p>For example, we can make a register machine support the instructions
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">assign ⟨</span><var><span class="pln">reg</span><span class="pun">₁</span></var><span class="pln">⟩ </span><span class="opn">(</span><span class="pln">op </span><span class="kwd">car</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg ⟨</span><var><span class="pln">reg</span><span class="pun">₂</span></var><span class="pln">⟩</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">assign ⟨</span><var><span class="pln">reg</span><span class="pun">₁</span></var><span class="pln">⟩ </span><span class="opn">(</span><span class="pln">op </span><span class="kwd">cdr</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg ⟨</span><var><span class="pln">reg</span><span class="pun">₂</span></var><span class="pln">⟩</span><span class="clo">))</span></pre></div>

<p>if we implement these, respectively, as
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">assign ⟨</span><var><span class="pln">reg</span><span class="pun">₁</span></var><span class="pln">⟩ 
        </span><span class="opn">(</span><span class="pln">op vector-ref</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">reg the-cars</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">reg ⟨</span><var><span class="pln">reg</span><span class="pun">₂</span></var><span class="pln">⟩</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">assign ⟨</span><var><span class="pln">reg</span><span class="pun">₁</span></var><span class="pln">⟩
        </span><span class="opn">(</span><span class="pln">op vector-ref</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">reg the-cdrs</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">reg ⟨</span><var><span class="pln">reg</span><span class="pun">₂</span></var><span class="pln">⟩</span><span class="clo">))</span></pre></div>

<p>The instructions
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">perform </span><span class="opn">(</span><span class="pln">op set-car!</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg ⟨</span><var><span class="pln">reg</span><span class="pun">₁</span></var><span class="pln">⟩</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg ⟨</span><var><span class="pln">reg</span><span class="pun">₂</span></var><span class="pln">⟩</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">perform </span><span class="opn">(</span><span class="pln">op set-cdr!</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg ⟨</span><var><span class="pln">reg</span><span class="pun">₁</span></var><span class="pln">⟩</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg ⟨</span><var><span class="pln">reg</span><span class="pun">₂</span></var><span class="pln">⟩</span><span class="clo">))</span></pre></div>

<p>are implemented as
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">perform </span><span class="opn">(</span><span class="pln">op vector-set!</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">reg the-cars</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">reg ⟨</span><var><span class="pln">reg</span><span class="pun">₁</span></var><span class="pln">⟩</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">reg ⟨</span><var><span class="pln">reg</span><span class="pun">₂</span></var><span class="pln">⟩</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">perform </span><span class="opn">(</span><span class="pln">op vector-set!</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">reg the-cdrs</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">reg ⟨</span><var><span class="pln">reg</span><span class="pun">₁</span></var><span class="pln">⟩</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">reg ⟨</span><var><span class="pln">reg</span><span class="pun">₂</span></var><span class="pln">⟩</span><span class="clo">))</span></pre></div>

<p><code>Cons</code> is performed by allocating an unused index and storing the
arguments to <code>cons</code> in <code>the-cars</code> and <code>the-cdrs</code> at that indexed
vector position.  We presume that there is a special register, <code>free</code>,
that always holds a pair pointer containing the next available index, and that
we can increment the index part of that pointer to find the next free
location.<a class="footnote_link" id="DOCF296" href="#FOOT296"><sup>296</sup></a>  For example, the instruction
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">assign ⟨</span><var><span class="pln">reg</span><span class="pun">₁</span></var><span class="pln">⟩
        </span><span class="opn">(</span><span class="pln">op </span><span class="kwd">cons</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">reg ⟨</span><var><span class="pln">reg</span><span class="pun">₂</span></var><span class="pln">⟩</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">reg ⟨</span><var><span class="pln">reg</span><span class="pun">₃</span></var><span class="pln">⟩</span><span class="clo">))</span></pre></div>

<p>is implemented as the following sequence of vector operations:<a class="footnote_link" id="DOCF297" href="#FOOT297"><sup>297</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">perform </span><span class="opn">(</span><span class="pln">op vector-set!</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">reg the-cars</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">reg free</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">reg ⟨</span><var><span class="pln">reg</span><span class="pun">₂</span></var><span class="pln">⟩</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">perform </span><span class="opn">(</span><span class="pln">op vector-set!</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">reg the-cdrs</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">reg free</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">reg ⟨</span><var><span class="pln">reg</span><span class="pun">₃</span></var><span class="pln">⟩</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">assign ⟨</span><var><span class="pln">reg</span><span class="pun">₁</span></var><span class="pln">⟩ </span><span class="opn">(</span><span class="pln">reg free</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">assign free </span><span class="opn">(</span><span class="pln">op </span><span class="pun">+</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg free</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">const </span><span class="lit">1</span><span class="clo">))</span></pre></div>

<p>The <code>eq?</code> operation
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">op </span><span class="kwd">eq</span><span class="pun">?</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg ⟨</span><var><span class="pln">reg</span><span class="pun">₁</span></var><span class="pln">⟩</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg ⟨</span><var><span class="pln">reg</span><span class="pun">₂</span></var><span class="pln">⟩</span><span class="clo">)</span></pre></div>

<p>simply tests the equality of all fields in the registers, and predicates such
as <code>pair?</code>, <code>null?</code>, <code>symbol?</code>, and <code>number?</code> need only
check the type field.
</p>
<a id="Implementing-stacks"></a>
<h5 class="subsubheading">Implementing stacks</h5>

<p>Although our register machines use stacks, we need do nothing special here,
since stacks can be modeled in terms of lists.  The stack can be a list of the
saved values, pointed to by a special register <code>the-stack</code>.  Thus, 
<code>(save ⟨<var>reg</var>⟩)</code> can be implemented as
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">assign the-stack 
        </span><span class="opn">(</span><span class="pln">op </span><span class="kwd">cons</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">reg ⟨</span><var><span class="pln">reg</span></var><span class="pln">⟩</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">reg the-stack</span><span class="clo">))</span></pre></div>

<p>Similarly, <code>(restore ⟨<var>reg</var>⟩)</code> can be implemented as
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">assign ⟨</span><var><span class="pln">reg</span></var><span class="pln">⟩ </span><span class="opn">(</span><span class="pln">op </span><span class="kwd">car</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg the-stack</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">assign the-stack </span><span class="opn">(</span><span class="pln">op </span><span class="kwd">cdr</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg the-stack</span><span class="clo">))</span></pre></div>

<p>and <code>(perform (op initialize-stack))</code> can be implemented as
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">assign the-stack </span><span class="opn">(</span><span class="pln">const </span><span class="opn">(</span><span class="clo">)))</span></pre></div>

<p>These operations can be further expanded in terms of the vector operations
given above.  In conventional computer architectures, however, it is usually
advantageous to allocate the stack as a separate vector.  Then pushing and
popping the stack can be accomplished by incrementing or decrementing an index
into that vector.
</p>
<blockquote>
<p><strong><a id="Exercise-5_002e20"></a>Exercise 5.20:</strong> Draw the box-and-pointer
representation and the memory-vector representation (as in <a href="#Figure-5_002e14">Figure 5.14</a>)
of the list structure produced by
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> x </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> y </span><span class="opn">(</span><span class="pln">list x x</span><span class="clo">))</span></pre></div>

<p>with the <code>free</code> pointer initially <code>p1</code>.  What is the final value of
<code>free</code>?  What pointers represent the values of <code>x</code> and <code>y</code>?
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-5_002e21"></a>Exercise 5.21:</strong> Implement register machines for
the following procedures.  Assume that the list-structure memory operations are
available as machine primitives.
</p>
<ol>
<li> Recursive <code>count-leaves</code>:

<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">count-leaves tree</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">null? tree</span><span class="clo">)</span><span class="pln"> </span><span class="lit">0</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">not </span><span class="opn">(</span><span class="pln">pair? tree</span><span class="clo">))</span><span class="pln"> </span><span class="lit">1</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="pln">count-leaves </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> tree</span><span class="clo">))</span><span class="pln">
            </span><span class="opn">(</span><span class="pln">count-leaves </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> tree</span><span class="clo">))))))</span></pre></div>

</li><li> Recursive <code>count-leaves</code> with explicit counter:

<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">count-leaves tree</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">count-iter tree n</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">null? tree</span><span class="clo">)</span><span class="pln"> n</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">((</span><span class="pln">not </span><span class="opn">(</span><span class="pln">pair? tree</span><span class="clo">))</span><span class="pln"> </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">))</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> 
           </span><span class="opn">(</span><span class="pln">count-iter 
            </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> tree</span><span class="clo">)</span><span class="pln">
            </span><span class="opn">(</span><span class="pln">count-iter </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> tree</span><span class="clo">)</span><span class="pln"> 
                        n</span><span class="clo">)))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">count-iter tree </span><span class="lit">0</span><span class="clo">))</span></pre></div>
</li></ol>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-5_002e22"></a>Exercise 5.22:</strong> <a href="3_002e3.xhtml#Exercise-3_002e12">Exercise 3.12</a> of 
<a href="3_002e3.xhtml#g_t3_002e3_002e1">3.3.1</a> presented an <code>append</code> procedure that appends two lists to form
a new list and an <code>append!</code> procedure that splices two lists together.
Design a register machine to implement each of these procedures.  Assume that
the list-structure memory operations are available as primitive operations.
</p></blockquote>

<a id="g_t5_002e3_002e2"></a>
<a id="Maintaining-the-Illusion-of-Infinite-Memory"></a>
<h4 class="subsection"><span class="secnum">5.3.2</span><span class="sectitle">Maintaining the Illusion of Infinite Memory</span></h4>

<p>The representation method outlined in <a href="#g_t5_002e3_002e1">5.3.1</a> solves the problem of
implementing list structure, provided that we have an infinite amount of
memory.  With a real computer we will eventually run out of free space in which
to construct new pairs.<a class="footnote_link" id="DOCF298" href="#FOOT298"><sup>298</sup></a>  However,
most of the pairs generated in a typical computation are used only to hold
intermediate results.  After these results are accessed, the pairs are no
longer needed—they are <a id="index-garbage"></a>
<em>garbage</em>.  For instance, the computation
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">accumulate 
 </span><span class="pun">+</span><span class="pln"> 
 </span><span class="lit">0</span><span class="pln">
 </span><span class="opn">(</span><span class="pln">filter odd? </span><span class="opn">(</span><span class="pln">enumerate-interval </span><span class="lit">0</span><span class="pln"> n</span><span class="clo">)))</span></pre></div>

<p>constructs two lists: the enumeration and the result of filtering the
enumeration.  When the accumulation is complete, these lists are no longer
needed, and the allocated memory can be reclaimed.  If we can arrange to
collect all the garbage periodically, and if this turns out to recycle memory
at about the same rate at which we construct new pairs, we will have preserved
the illusion that there is an infinite amount of memory.
</p>
<p>In order to recycle pairs, we must have a way to determine which allocated
pairs are not needed (in the sense that their contents can no longer influence
the future of the computation).  The method we shall examine for accomplishing
this is known as <a id="index-garbage-collection-1"></a>
<em>garbage collection</em>.  Garbage collection is based on
the observation that, at any moment in a Lisp interpretation, the only objects
that can affect the future of the computation are those that can be reached by
some succession of <code>car</code> and <code>cdr</code> operations starting from the
pointers that are currently in the machine registers.<a class="footnote_link" id="DOCF299" href="#FOOT299"><sup>299</sup></a>
Any memory cell that is not so accessible may be recycled.
</p>
<p>There are many ways to perform garbage collection.  The method we shall examine
here is called <a id="index-stop_002dand_002dcopy"></a>
<em>stop-and-copy</em>.  The basic idea is to divide memory
into two halves: “working memory” and “free memory.”  When <code>cons</code>
constructs pairs, it allocates these in working memory.  When working memory is
full, we perform garbage collection by locating all the useful pairs in working
memory and copying these into consecutive locations in free memory.  (The
useful pairs are located by tracing all the <code>car</code> and <code>cdr</code> pointers,
starting with the machine registers.)  Since we do not copy the garbage, there
will presumably be additional free memory that we can use to allocate new
pairs.  In addition, nothing in the working memory is needed, since all the
useful pairs in it have been copied.  Thus, if we interchange the roles of
working memory and free memory, we can continue processing; new pairs will be
allocated in the new working memory (which was the old free memory).  When this
is full, we can copy the useful pairs into the new free memory (which was the
old working memory).<a class="footnote_link" id="DOCF300" href="#FOOT300"><sup>300</sup></a>
</p>
<a id="Implementation-of-a-stop_002dand_002dcopy-garbage-collector"></a>
<h5 class="subsubheading">Implementation of a stop-and-copy garbage collector</h5>

<p>We now use our register-machine language to describe the stop-and-copy
algorithm in more detail.  We will assume that there is a register called
<code>root</code> that contains a pointer to a structure that eventually points at
all accessible data.  This can be arranged by storing the contents of all the
machine registers in a pre-allocated list pointed at by <code>root</code> just before
starting garbage collection.<a class="footnote_link" id="DOCF301" href="#FOOT301"><sup>301</sup></a> We also assume that, in addition to the current
working memory, there is free memory available into which we can copy the
useful data.  The current working memory consists of vectors whose base
addresses are in registers called <code>the-cars</code> and <code>the-cdrs</code>, and the
free memory is in registers called <code>new-cars</code> and <code>new-cdrs</code>.
</p>
<p>Garbage collection is triggered when we exhaust the free cells in the current
working memory, that is, when a <code>cons</code> operation attempts to increment the
<code>free</code> pointer beyond the end of the memory vector.  When the
garbage-collection process is complete, the <code>root</code> pointer will point into
the new memory, all objects accessible from the <code>root</code> will have been
moved to the new memory, and the <code>free</code> pointer will indicate the next
place in the new memory where a new pair can be allocated.  In addition, the
roles of working memory and new memory will have been interchanged—new pairs
will be constructed in the new memory, beginning at the place indicated by
<code>free</code>, and the (previous) working memory will be available as the new
memory for the next garbage collection.  <a href="#Figure-5_002e15">Figure 5.15</a> shows the
arrangement of memory just before and just after garbage collection.
</p>
<figure class="float">
<a id="Figure-5_002e15"></a>
<object style="width: 57.59ex; height: 44.47ex;" data="fig/chap5/Fig5.15c.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 5.15:</strong> Reconfiguration of memory by the garbage-collection process.</p>
</figcaption>
</figure>

<p>The state of the garbage-collection process is controlled by maintaining two
pointers: <code>free</code> and <code>scan</code>.  These are initialized to point to the
beginning of the new memory.  The algorithm begins by relocating the pair
pointed at by <code>root</code> to the beginning of the new memory.  The pair is
copied, the <code>root</code> pointer is adjusted to point to the new location, and
the <code>free</code> pointer is incremented.  In addition, the old location of the
pair is marked to show that its contents have been moved.  This marking is done
as follows: In the <code>car</code> position, we place a special tag that signals
that this is an already-moved object.  (Such an object is traditionally called
a <a id="index-broken-heart"></a>
<em>broken heart</em>.)<a class="footnote_link" id="DOCF302" href="#FOOT302"><sup>302</sup></a>  In the <code>cdr</code> position
we place a <a id="index-forwarding-address"></a>
<em>forwarding address</em> that points at the location to which
the object has been moved.
</p>
<p>After relocating the root, the garbage collector enters its basic cycle.  At
each step in the algorithm, the <code>scan</code> pointer (initially pointing at the
relocated root) points at a pair that has been moved to the new memory but
whose <code>car</code> and <code>cdr</code> pointers still refer to objects in the old
memory.  These objects are each relocated, and the <code>scan</code> pointer is
incremented.  To relocate an object (for example, the object indicated by the
<code>car</code> pointer of the pair we are scanning) we check to see if the object
has already been moved (as indicated by the presence of a broken-heart tag in
the <code>car</code> position of the object).  If the object has not already been
moved, we copy it to the place indicated by <code>free</code>, update <code>free</code>,
set up a broken heart at the object’s old location, and update the pointer to
the object (in this example, the <code>car</code> pointer of the pair we are
scanning) to point to the new location.  If the object has already been moved,
its forwarding address (found in the <code>cdr</code> position of the broken heart)
is substituted for the pointer in the pair being scanned.  Eventually, all
accessible objects will have been moved and scanned, at which point the
<code>scan</code> pointer will overtake the <code>free</code> pointer and the process will
terminate.
</p>
<p>We can specify the stop-and-copy algorithm as a sequence of instructions for a
register machine.  The basic step of relocating an object is accomplished by a
subroutine called <code>relocate-old-result-in-new</code>.  This subroutine gets its
argument, a pointer to the object to be relocated, from a register named
<code>old</code>.  It relocates the designated object (incrementing <code>free</code> in
the process), puts a pointer to the relocated object into a register called
<code>new</code>, and returns by branching to the entry point stored in the register
<code>relocate-continue</code>.  To begin garbage collection, we invoke this
subroutine to relocate the <code>root</code> pointer, after initializing <code>free</code>
and <code>scan</code>.  When the relocation of <code>root</code> has been accomplished, we
install the new pointer as the new <code>root</code> and enter the main loop of the
garbage collector.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">begin-garbage-collection
  </span><span class="opn">(</span><span class="pln">assign free </span><span class="opn">(</span><span class="pln">const </span><span class="lit">0</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign scan </span><span class="opn">(</span><span class="pln">const </span><span class="lit">0</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign old </span><span class="opn">(</span><span class="pln">reg root</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign relocate-continue 
          </span><span class="opn">(</span><span class="pln">label reassign-root</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label relocate-old-result-in-new</span><span class="clo">))</span><span class="pln">
reassign-root
  </span><span class="opn">(</span><span class="pln">assign root </span><span class="opn">(</span><span class="pln">reg new</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label gc-loop</span><span class="clo">))</span></pre></div>

<p>In the main loop of the garbage collector we must determine whether there are
any more objects to be scanned.  We do this by testing whether the <code>scan</code>
pointer is coincident with the <code>free</code> pointer.  If the pointers are equal,
then all accessible objects have been relocated, and we branch to
<code>gc-flip</code>, which cleans things up so that we can continue the interrupted
computation.  If there are still pairs to be scanned, we call the relocate
subroutine to relocate the <code>car</code> of the next pair (by placing the
<code>car</code> pointer in <code>old</code>).  The <code>relocate-continue</code> register is
set up so that the subroutine will return to update the <code>car</code> pointer.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">gc-loop
  </span><span class="opn">(</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op </span><span class="pun">=</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg scan</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg free</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label gc-flip</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign old 
          </span><span class="opn">(</span><span class="pln">op vector-ref</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">reg new-cars</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">reg scan</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign relocate-continue 
          </span><span class="opn">(</span><span class="pln">label update-car</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label relocate-old-result-in-new</span><span class="clo">))</span></pre></div>

<p>At <code>update-car</code>, we modify the <code>car</code> pointer of the pair being
scanned, then proceed to relocate the <code>cdr</code> of the pair.  We return to
<code>update-cdr</code> when that relocation has been accomplished.  After relocating
and updating the <code>cdr</code>, we are finished scanning that pair, so we continue
with the main loop.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">update-car
  </span><span class="opn">(</span><span class="pln">perform </span><span class="opn">(</span><span class="pln">op vector-set!</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">reg new-cars</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">reg scan</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">reg new</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign  old 
           </span><span class="opn">(</span><span class="pln">op vector-ref</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">reg new-cdrs</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">reg scan</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign  relocate-continue
           </span><span class="opn">(</span><span class="pln">label update-cdr</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label relocate-old-result-in-new</span><span class="clo">))</span><span class="pln">
update-cdr
  </span><span class="opn">(</span><span class="pln">perform </span><span class="opn">(</span><span class="pln">op vector-set!</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">reg new-cdrs</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">reg scan</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">reg new</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign  scan </span><span class="opn">(</span><span class="pln">op </span><span class="pun">+</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg scan</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">const </span><span class="lit">1</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label gc-loop</span><span class="clo">))</span></pre></div>

<p>The subroutine <code>relocate-old-result-in-new</code> relocates objects as follows:
If the object to be relocated (pointed at by <code>old</code>) is not a pair, then we
return the same pointer to the object unchanged (in <code>new</code>).  (For example,
we may be scanning a pair whose <code>car</code> is the number 4.  If we represent
the <code>car</code> by <code>n4</code>, as described in <a href="#g_t5_002e3_002e1">5.3.1</a>, then we want
the “relocated” <code>car</code> pointer to still be <code>n4</code>.)  Otherwise, we
must perform the relocation.  If the <code>car</code> position of the pair to be
relocated contains a broken-heart tag, then the pair has in fact already been
moved, so we retrieve the forwarding address (from the <code>cdr</code> position of
the broken heart) and return this in <code>new</code>.  If the pointer in <code>old</code>
points at a yet-unmoved pair, then we move the pair to the first free cell in
new memory (pointed at by <code>free</code>) and set up the broken heart by storing a
broken-heart tag and forwarding address at the old location.
<code>Relocate-old-result-in-new</code> uses a register <code>oldcr</code> to hold the
<code>car</code> or the <code>cdr</code> of the object pointed at by
<code>old</code>.<a class="footnote_link" id="DOCF303" href="#FOOT303"><sup>303</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">relocate-old-result-in-new
  </span><span class="opn">(</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op pointer-to-pair?</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg old</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label pair</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign new </span><span class="opn">(</span><span class="pln">reg old</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">reg relocate-continue</span><span class="clo">))</span><span class="pln">
pair
  </span><span class="opn">(</span><span class="pln">assign  oldcr 
           </span><span class="opn">(</span><span class="pln">op vector-ref</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">reg the-cars</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">reg old</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op broken-heart?</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg oldcr</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">branch  </span><span class="opn">(</span><span class="pln">label already-moved</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign  new </span><span class="opn">(</span><span class="pln">reg free</span><span class="clo">))</span><span class="pln"> </span><span class="roman"><span class="com">; new location for pair</span></span><span class="pln">
  </span><span class="roman"><span class="com">;; Update </span><code><span class="com">free</span></code><span class="com"> pointer.</span></span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign free </span><span class="opn">(</span><span class="pln">op </span><span class="pun">+</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg free</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">const </span><span class="lit">1</span><span class="clo">))</span><span class="pln">
  </span><span class="roman"><span class="com">;; Copy the </span><code><span class="com">car</span></code><span class="com"> and </span><code><span class="com">cdr</span></code><span class="com"> to new memory.</span></span><span class="pln">
  </span><span class="opn">(</span><span class="pln">perform </span><span class="opn">(</span><span class="pln">op vector-set!</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">reg new-cars</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">reg new</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">reg oldcr</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign  oldcr 
           </span><span class="opn">(</span><span class="pln">op vector-ref</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">reg the-cdrs</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">reg old</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">perform </span><span class="opn">(</span><span class="pln">op vector-set!</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">reg new-cdrs</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">reg new</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">reg oldcr</span><span class="clo">))</span><span class="pln">
  </span><span class="roman"><span class="com">;; Construct the broken heart.</span></span><span class="pln">
  </span><span class="opn">(</span><span class="pln">perform </span><span class="opn">(</span><span class="pln">op vector-set!</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">reg the-cars</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">reg old</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">const broken-heart</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">perform </span><span class="opn">(</span><span class="pln">op vector-set!</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">reg the-cdrs</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">reg old</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">reg new</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">reg relocate-continue</span><span class="clo">))</span><span class="pln">
already-moved
  </span><span class="opn">(</span><span class="pln">assign  new
           </span><span class="opn">(</span><span class="pln">op vector-ref</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">reg the-cdrs</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">reg old</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">reg relocate-continue</span><span class="clo">))</span></pre></div>

<p>At the very end of the garbage-collection process, we interchange the role of
old and new memories by interchanging pointers: interchanging <code>the-cars</code>
with <code>new-cars</code>, and <code>the-cdrs</code> with <code>new-cdrs</code>.  We will then
be ready to perform another garbage collection the next time memory runs out.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">gc-flip
  </span><span class="opn">(</span><span class="pln">assign temp </span><span class="opn">(</span><span class="pln">reg the-cdrs</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign the-cdrs </span><span class="opn">(</span><span class="pln">reg new-cdrs</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign new-cdrs </span><span class="opn">(</span><span class="pln">reg temp</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign temp </span><span class="opn">(</span><span class="pln">reg the-cars</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign the-cars </span><span class="opn">(</span><span class="pln">reg new-cars</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign new-cars </span><span class="opn">(</span><span class="pln">reg temp</span><span class="clo">))</span></pre></div>

<div class="footnote">
<h4 class="footnotes-heading">Footnotes</h4>

<div id="FOOT290"><p><a class="footnote_backlink" href="#DOCF290"><sup>290</sup></a>
We could represent memory as
lists of items.  However, the access time would then not be independent of the
index, since accessing the <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>n</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mtext>th</mtext>
    </mrow>
  </msup>
</math> element of a list requires <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>−<!-- − --></mo>
    <mn>1</mn>
  </mrow>
</math>
<code>cdr</code> operations.</p>
</div>
<div id="FOOT291"><p><a class="footnote_backlink" href="#DOCF291"><sup>291</sup></a>
For
completeness, we should specify a <code>make-vector</code> operation that constructs
vectors.  However, in the present application we will use vectors only to model
fixed divisions of the computer memory.</p>
</div>
<div id="FOOT292"><p><a class="footnote_backlink" href="#DOCF292"><sup>292</sup></a>
This is precisely the same
“tagged data” idea we introduced in <a href="Chapter-2.xhtml#Chapter-2">Chapter 2</a> for dealing with generic
operations.  Here, however, the data types are included at the primitive
machine level rather than constructed through the use of lists.</p>
</div>
<div id="FOOT293"><p><a class="footnote_backlink" href="#DOCF293"><sup>293</sup></a>
Type information
may be encoded in a variety of ways, depending on the details of the machine on
which the Lisp system is to be implemented.  The execution efficiency of Lisp
programs will be strongly dependent on how cleverly this choice is made, but it
is difficult to formulate general design rules for good choices.  The most
straightforward way to implement typed pointers is to allocate a fixed set of
bits in each pointer to be a <a id="index-type-field"></a>
<em>type field</em> that encodes the data type.
Important questions to be addressed in designing such a representation include
the following: How many type bits are required?  How large must the vector
indices be?  How efficiently can the primitive machine instructions be used to
manipulate the type fields of pointers?  Machines that include special hardware
for the efficient handling of type fields are said to have <a id="index-tagged-architectures"></a>
<em>tagged architectures</em>.</p>
</div>
<div id="FOOT294"><p><a class="footnote_backlink" href="#DOCF294"><sup>294</sup></a>
This decision on the representation of numbers determines whether
<code>eq?</code>, which tests equality of pointers, can be used to test for equality
of numbers.  If the pointer contains the number itself, then equal numbers will
have the same pointer.  But if the pointer contains the index of a location
where the number is stored, equal numbers will be guaranteed to have equal
pointers only if we are careful never to store the same number in more than one
location.</p>
</div>
<div id="FOOT295"><p><a class="footnote_backlink" href="#DOCF295"><sup>295</sup></a>
This is just like writing a number
as a sequence of digits, except that each “digit” is a number between 0 and
the largest number that can be stored in a single pointer.</p>
</div>
<div id="FOOT296"><p><a class="footnote_backlink" href="#DOCF296"><sup>296</sup></a>
There are other ways of finding free storage.  For example,
we could link together all the unused pairs into a <a id="index-free-list"></a>
<em>free list</em>.  Our
free locations are consecutive (and hence can be accessed by incrementing a
pointer) because we are using a compacting garbage collector, as we will see in
<a href="#g_t5_002e3_002e2">5.3.2</a>.</p>
</div>
<div id="FOOT297"><p><a class="footnote_backlink" href="#DOCF297"><sup>297</sup></a>
This is
essentially the implementation of <code>cons</code> in terms of <code>set-car!</code> and
<code>set-cdr!</code>, as described in <a href="3_002e3.xhtml#g_t3_002e3_002e1">3.3.1</a>.  The operation
<code>get-new-pair</code> used in that implementation is realized here by the
<code>free</code> pointer.</p>
</div>
<div id="FOOT298"><p><a class="footnote_backlink" href="#DOCF298"><sup>298</sup></a>
This may not be true eventually, because
memories may get large enough so that it would be impossible to run out of free
memory in the lifetime of the computer.  For example, there are about
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mn>3</mn>
    <mo>⋅<!-- ⋅ --></mo>
    <msup>
      <mn>10</mn>
      <mrow class="MJX-TeXAtom-ORD">
        <mn>13</mn>
      </mrow>
    </msup>
  </mrow>
</math> microseconds in a year, so if we were to <code>cons</code> once per
microsecond we would need about <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mn>10</mn>
    <mrow class="MJX-TeXAtom-ORD">
      <mn>15</mn>
    </mrow>
  </msup>
</math> cells of memory to build a machine that
could operate for 30 years without running out of memory.  That much memory
seems absurdly large by today’s standards, but it is not physically impossible.
On the other hand, processors are getting faster and a future computer may have
large numbers of processors operating in parallel on a single memory, so it may
be possible to use up memory much faster than we have postulated.</p>
</div>
<div id="FOOT299"><p><a class="footnote_backlink" href="#DOCF299"><sup>299</sup></a>
We assume here
that the stack is represented as a list as described in <a href="#g_t5_002e3_002e1">5.3.1</a>, so
that items on the stack are accessible via the pointer in the stack register.</p>
</div>
<div id="FOOT300"><p><a class="footnote_backlink" href="#DOCF300"><sup>300</sup></a>
This idea was invented and first implemented by
Minsky, as part of the implementation of Lisp for the PDP-1 at the
<abbr>MIT</abbr> Research Laboratory of Electronics.  It was further developed by
<a href="References.xhtml#Fenichel-and-Yochelson-_00281969_0029">Fenichel and Yochelson (1969)</a> for use in the Lisp implementation for the
Multics time-sharing system.  Later, <a href="References.xhtml#Baker-_00281978_0029">Baker (1978)</a> developed a “real-time”
version of the method, which does not require the computation to stop during
garbage collection.  Baker’s idea was extended by Hewitt, Lieberman, and Moon
(see <a href="References.xhtml#Lieberman-and-Hewitt-1983">Lieberman and Hewitt 1983</a>) to take advantage of the fact that some
structure is more volatile and other structure is more permanent.
</p>
<p>An alternative commonly used garbage-collection technique is the
<a id="index-mark_002dsweep"></a>
<em>mark-sweep</em> method.  This consists of tracing all the structure
accessible from the machine registers and marking each pair we reach.  We then
scan all of memory, and any location that is unmarked is “swept up” as
garbage and made available for reuse.  A full discussion of the mark-sweep
method can be found in <a href="References.xhtml#Allen-1978">Allen 1978</a>.
</p>
<p>The Minsky-Fenichel-Yochelson algorithm is the dominant algorithm in use for
large-memory systems because it examines only the useful part of memory.  This
is in contrast to mark-sweep, in which the sweep phase must check all of
memory.  A second advantage of stop-and-copy is that it is a
<a id="index-compacting"></a>
<em>compacting</em> garbage collector.  That is, at the end of the
garbage-collection phase the useful data will have been moved to consecutive
memory locations, with all garbage pairs compressed out.  This can be an
extremely important performance consideration in machines with virtual memory,
in which accesses to widely separated memory addresses may require extra paging
operations.</p>
</div>
<div id="FOOT301"><p><a class="footnote_backlink" href="#DOCF301"><sup>301</sup></a>
This list of registers does not include
the registers used by the storage-allocation system—<code>root</code>,
<code>the-cars</code>, <code>the-cdrs</code>, and the other registers that will be
introduced in this section.</p>
</div>
<div id="FOOT302"><p><a class="footnote_backlink" href="#DOCF302"><sup>302</sup></a>
The term <em>broken heart</em> was coined by
David Cressey, who wrote a garbage collector for MDL, a dialect of Lisp
developed at <abbr>MIT</abbr> during the early 1970s.</p>
</div>
<div id="FOOT303"><p><a class="footnote_backlink" href="#DOCF303"><sup>303</sup></a>
The garbage collector uses the low-level predicate
<code>pointer-to-pair?</code> instead of the list-structure <code>pair?</code>  operation
because in a real system there might be various things that are treated as
pairs for garbage-collection purposes.  For example, in a Scheme system that
conforms to the <abbr>IEEE</abbr> standard a procedure object may be implemented
as a special kind of “pair” that doesn’t satisfy the <code>pair?</code> predicate.
For simulation purposes, <code>pointer-to-pair?</code> can be implemented as
<code>pair?</code>.</p>
</div>
</div>
<nav class="header">
<p>
Next: <a href="5_002e4.xhtml#g_t5_002e4" accesskey="n" rel="next">5.4</a>, Prev: <a href="5_002e2.xhtml#g_t5_002e2" accesskey="p" rel="prev">5.2</a>, Up: <a href="#g_t5_002e3" accesskey="u" rel="prev">5.3</a>   [<a href="index.xhtml#SEC_Contents" title="Table of contents" accesskey="c" rel="contents">Contents</a>]</p>
</nav>


</section><span class="bottom jump" title="Jump to bottom"><a href="#pagebottom" accesskey="b">⇣</a></span><a id="pagebottom"></a>
</body>
</html>